package com.xzx.simple;

import org.junit.Test;

import java.util.*;

/**
 * @className com.xzx.simple algorithm
 * @description:有效的括号
 * @author: xzx
 * @date: 19-3-25 20:53
 * @version: v1
 */
public class EffectiveParentheses {
    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 示例 1:
     * 输入: "()"
     * 输出: true
     *
     * 示例 2:
     * 输入: "()[]{}"
     * 输出: true
     *
     * 示例 3:
     * 输入: "(]"
     * 输出: false
     *
     * 示例 4:
     * 输入: "([)]"
     * 输出: false
     *
     * 示例 5:
     * 输入: "{[]}"
     * 输出: true
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        return false;
    }

    private static Map<Character,Character> left = new HashMap<>();
    private static Map<Character,Character> right = new HashMap<>();
    static {
        left.put('(',')');
        left.put('{','}');
        left.put('[',']');

        right.put(')','(');
        right.put('}','{');
        right.put(']','[');
    }

    /**
     * 第一次尝试，暴力循环
     * 提交时间	状态	执行用时	内存消耗	语言
     * 几秒前	通过	116 ms	35.8 MB	java
     * @param s
     * @return
     */
    public boolean isValid1(String s) {
        if(null == s || s.length()%2 != 0){
            return false;
        }
        if(  s.equals("") ){
            return true;
        }
        char[] cs = s.toCharArray();
        if (right.containsKey(cs[0])){
            return false;
        }
        if (left.containsKey(cs[cs.length-1])){
            return false;
        }
        List<Character> cli = new ArrayList() ;
        for (char c: cs) {
            cli.add(c);
        }
        while(cli.size() != 0){
            for ( int le = 0; le < cli.size(); le ++){
                int ri = le+1;
                if (le == cli.size()-1){
                    break;
                }
                // 当前下
                if (right.containsKey(cli.get(ri))){
                    if(cli.get(le).equals(right.get(cli.get(ri)))){
                        cli.remove(ri);
                        cli.remove(le);
                        break;
                    }else {
                        return false;
                    }
                }
            }
        }
        return true;
    }


    /**
     * 测试类
     */
    @Test
    public void test(){
        String[] li = {"(([]){})", "()[]{}","(]","{[]}","([)]"};
        for (String s:li) {
            System.out.println(s+"的结果为："+isValid1(s));
        }
    }

}
